/*****************************************************************************
 * Source code information 
 * -----------------------
 * Original author    Ian Dickinson, HP Labs Bristol
 * Author email       ian_dickinson@users.sourceforge.net
 * Package            Jena 2
 * Web                http://sourceforge.net/projects/jena/
 * Created            25-Jul-2003
 * Filename           $RCSfile: DescribeClass.java,v $
 * Revision           $Revision: 1.4 $
 * Release status     $State: Exp $
 *
 * Last modified on   $Date: 2009/10/06 13:04:44 $
 *               by   $Author: ian_dickinson $
 *
 * (c) Copyright 2002, 2003, 2004, 2005 Hewlett-Packard Development Company, LP
 * (see footer for full conditions)
 *****************************************************************************/

// Package
///////////////
package semmatch;

// Imports
///////////////
import java.util.*;

import com.hp.hpl.jena.ontology.*;


public class ClassHierarchy{

    private Map<String,Concept> concepts=new HashMap<String,Concept>();
    private Set<Relation> relations=new TreeSet<Relation>();
    
    public void describeClass(OntClass cls) {
        try{
        String parentid;
        if (!cls.isAnon())
            parentid=cls.getLocalName();
        else
            parentid=cls.getId().toString();
        Concept parent=concepts.get(parentid);

        LinkedList<OntClass> queue=new LinkedList<OntClass>();
        for (Iterator<OntClass> i = cls.listSubClasses( true ); i.hasNext(); ) {
            OntClass child=i.next();
            String childid;
            if (!child.isAnon())
                childid=child.getLocalName();
            else
                childid=child.getId().toString();
            if (concepts.containsKey(childid))
            {
                Concept c=concepts.get(childid);
                c.addParent(0, parent );                
                for (int j=0;j<Constants.MAX_DEPTH-1;j++)
                {                    
                      c.addAncestors(j+1, parent.parents[j]);
                }
                queue.add(child);
            }
            else
            {
                Concept c=new Concept(childid,parent.getMindepth()+1);
                c.addParent(0, parent);
                for (int j=0;j<Constants.MAX_DEPTH-1;j++)
                {
                       c.addAncestors(j+1, parent.parents[j]);
                }
                concepts.put(childid, c);
                queue.add(child);
            }
        }
        for (OntClass ocls:queue){
            describeClass(ocls);
        }
        }
        catch (Exception e)
        {}
    }

   public void put(String id,Concept c)
    {
        concepts.put(id,c);
   }
   public void listConcepts()
   {
        for (String id:concepts.keySet())
        {
            Concept c=concepts.get(id);
            System.out.print(id.toString()+": ");
            for (int i=0;i<Constants.MAX_DEPTH;i++)
            {
                System.out.print(i+"->");
                if (!c.parents[i].isEmpty())
                    for (Object p:c.parents[i]){
                        System.out.print(((Concept)p).getId()+",");
                    }
            }
            System.out.println();
        }
   }
   public boolean containsKey(String key)
    {
        return concepts.containsKey(key);
   }
   public Concept find(String key)
    {
        return concepts.get(key);
   }
   Set<Concept> replace_with_parents(Set<Concept> Q)
    {
        Set<Concept> pQ=new TreeSet<Concept>();
        int min_depth=1;
        for (Concept con:Q)
           if (!con.parents[0].isEmpty())
           for (Object p:con.parents[0])
                if (((Concept) p).getMindepth()>min_depth)
                    pQ.add((Concept)p);
        return pQ;
   }
   public Set<Concept> extractParents(Concept c1,Concept c2)
   {       
        Set<Concept> Q1=new TreeSet<Concept>();
        Set<Concept> Q2=new TreeSet<Concept>();
        Set<Concept> anc=new TreeSet<Concept>();
//        if (!c1.parents[0].isEmpty())
//             Q1.addAll(c1.parents[0]);
        Q1.add(c1);
        Q2.add(c2);
//        if (!c2.parents[0].isEmpty())
//             Q2.addAll(c2.parents[0]);
        int d=0;
        int mina=c1.getMindepth()-1;
        int maxa=c1.getMaxdepth()-1;
        int minb=c2.getMindepth()-1;
        int maxb=c2.getMaxdepth()-1;
        int min_depth=1;
        int x1=0,x2=0;
        while ((!Q1.isEmpty())&&(!Q2.isEmpty())&&(!(Q1.containsAll(Q2)&&Q2.containsAll(Q1)))&&(x1<Constants.MAX_DEPTH)&&(x2<Constants.MAX_DEPTH))
        {
            if (minb>maxa){
                    Q2=replace_with_parents(Q2);
                    maxb--;
                    minb--;
                    x1++;

            }
            else if (mina>maxb){
                    Q1=replace_with_parents(Q1);
                    maxa--;
                    mina--;
                    x2++;
            }
            else {
                         Set<Concept> M=new TreeSet();
                         for (Concept c:Q1)
                         if (Q2.contains(c))
                             M.add(c);

                         if (!M.isEmpty()){
                            for (Concept e:M){
                                    anc.add(e);
                                Q1.remove(e);
                                Q2.remove(e);
                            }
                         
                         }
                     else {
                       Set<Concept> nQ1=new TreeSet<Concept>();
                        Set<Concept> nQ2=new TreeSet<Concept>();
//                    for (Concept e:Q1)
//                        if (e.getMaxdepth()==maxa){
//                            nQ1.addAll(e.parents[0]);
//                           // nQ1.add(e);
//                        }
//                        else
//                            nQ1.add(e);
//                    for (Concept e:Q2)
//                        if (e.getMaxdepth()==maxb){
//                            nQ2.addAll(e.parents[0]);
//                            //nQ2.add(e);
//                        }
//                        else
//                            nQ2.add(e);
 //                   
                     for (Concept e:Q1)
                         if (!e.parents[0].isEmpty()){
                           //  if (e.getMaxdepth()==maxa)
                                nQ1.addAll(e.parents[0]);
                           //  else
                                nQ1.add(e);
                         }
                     for (Concept e:Q2){
                         if (!e.parents[0].isEmpty())
                           //  if (e.getMaxdepth()==maxb)
                                nQ2.addAll(e.parents[0]);
                           //  else
                                nQ1.add(e);
                         }
                     Q1=nQ1;Q2=nQ2;
                    mina=minDepth(Q1);
                    minb=minDepth(Q2);
                    maxa=maxDepth(Q1);
                    maxb=maxDepth(Q2);
                    x1++;
                    x2++;
                }
                }
            }
        if ((Q1.containsAll(Q2)&&Q2.containsAll(Q1)))
            anc.addAll(Q1);
        return anc;
//        System.out.println("Common parents");
//        for (Concept e:anc){
//            System.out.println(e.getId());
//        }
   }

    private int minDepth(Set<Concept> Q1) {
        int min=1000;
        for (Concept c:Q1)
            if (c.getMindepth()<min)
                min=c.getMindepth();
        return min;
    }

    private int maxDepth(Set<Concept> Q1) {
        int max=0;
        for (Concept c:Q1)
            if (c.getMaxdepth()>max)
                max=c.getMaxdepth();
        return max;
    }
      public  double cmv(Concept c1,Concept c2)
    {
        Set<Concept> anc=extractParents(c1,c2);
           Set<Concept> fset=new TreeSet<Concept>(anc);
        for (Concept e:anc)
        {
            for (Concept e2:anc)
                if (e.isAncestor(Constants.MAX_DEPTH-1, e2))
                    fset.remove(e2);
        }
        double concept_match=0;
        for (Concept e:fset){
            concept_match+=(c1.appartenance(e)+c2.appartenance(e))/2.0;
        }
        return concept_match;
    }
    public void addRelation(ObjectProperty p)
    {
       Concept c1,c2;
       Relation r;
        if (p.getDomain().isAnon())
                c1=find(p.getDomain().getId().toString());
        else
                c1=find(p.getDomain().getLocalName());
        if (p.getRange().isAnon())
                c2=find(p.getRange().getId().toString());
        else
                c2=find(p.getRange().getLocalName());
        if (p.isAnon())
            r=new Relation(p.getId().toString(),c1,c2);
        else
            r=new Relation(p.getLocalName(),c1,c2);
        relations.add(r);
    }
    public double cmh(Concept c1,Concept c2,int h)
    {
       Set<Concept> C1=new TreeSet<Concept>();
       Set<Concept> C2=new TreeSet<Concept>();
       Set<Matching> Matches=new TreeSet<Matching>();
        for (Relation r:relations)
        {
            if (r.getDomain().equals(c1)) C1.add(r.getRange());
             if (r.getDomain().equals(c2)) C2.add(r.getRange());
        }
        ////////////////
        //daca nici una nu participa la relatii orizontale, ne intereseaza doar matching-ul vertical
        if(C1.size() == 0 && C2.size() == 0)
            return -1.0;
        /////////////////
      for (Concept e1:C1)
          for (Concept e2:C2)
          {
            double value=cm(c1,c2,h-1);
            Matches.add(new Matching(c1,c2,value));
          }
      double maximalMatch=Hungarian(Matches);
      return maximalMatch;
    }
    public double cm(Concept c1,Concept c2,int h)
    {
        if (h>0)
        {
            double vv = cmv(c1,c2);
            double hh = cmh(c1,c2,h);
            if(hh < -0.1){
                return vv;
            }else{
                //System.out.println("Avem si matching orizontal");
                return vv * Constants.ALPHA + hh * (1 - Constants.ALPHA);
            }
        }
        else return 0;
    }

    static double Hungarian(Set<Matching> matches) {
        if(matches.size() == 0){
            return 0.0;
        }
        List<Concept> domain = new ArrayList<Concept>();
        List<Concept> codomain = new ArrayList<Concept>();
        for(Matching match : matches){
            Concept c1 = match.getC1();
            Concept c2 = match.getC2();
            if(!domain.contains(c1))
                domain.add(c1);
            if(!codomain.contains(c2))
                codomain.add(c2);
        }
        System.out.println(domain.size() + " " + codomain.size() );
        double[][] mat = new double[domain.size()][codomain.size()];
        for(Matching match : matches){
            Concept c1 = match.getC1();
            Concept c2 = match.getC2();
            double val = 1 - match.getValue();
            mat[domain.indexOf(c1)][codomain.indexOf(c2)] = val;
        }
        //int[][] result = new HungarianAlgorithm().computeAssignments(mat);
        int[][] result = HungarianAlgorithm.hgAlgorithm(mat, "");
        double avg = 0;
        for(int i=0; i<result.length; ++i){
            int i1 = result[i][0];
            int i2 = result[i][1];
            avg += (1.0 - mat[i1][i2]);
        }
        avg /= result.length;
        return avg;
    }
}




